perm filename 28A[00,BGB] blob
sn#046274 filedate 1973-06-06 generic text, type T, neo UTF8
~F83. NESTING.
Let the given polygon be named Poly; and let the surrounder
of Poly be called Exopoly; and assume that Exopoly surrounds several
enclaved polygons called "endo's", which are already in the nested
polygon tree. Also, there are two kinds of temporary lists named the
PLIST and the NLIST. There is one PLIST which is initially a list of
all the ENDO polygons on Exopoly's ENDO ring. Each endo in turn has
an NLIST which is initially empty. The subroutine INTREE re-scans
the sky array for the polygon due east of the uppermost left vector
of each endo polygon on the PLIST, (Exopoly's ENDO ring). On such
re-scanning, (on behalf of say an Endo1), there are four cases:
1. No change; the scan returns Exopoly;
which is Endo1's original EXO.
2. Poly captures Endo1; the scan returns Poly indicating
that endo1 has been captured by Poly.
3. My brothers fate; the scan hits an endo2 which
is not on the PLIST; which means that endo2's EXO is valid
and is the valid EXO of endo1.
4. My fate delayed; the scan hits an endo2 which is still
on the PLIST; which means that endo2's EXO is not yet
valid but when discovered it will also be Endo1's EXO;
so Endo1 is CONS'ed into Endo2's NLIST.
When an endo polygon's EXO has been re-discovered, then all the
polygons on that endo's NLIST are also placed into the polygon tree
at that place. All of this link crunching machinery takes half a page
of code and is not frequently executed.
KRAKAUER'S NESTING ALGORITHM.
~I1973,800;F8- 28 -~
M400;F2
"The image tree is generated one threshold level at a time, starting at the
highest level (branch tips). At each level, the image is scanned, and the points
above the threshold are marked in a scratch array. This scatch array is then scanned
for marked points. When one is found, a contiguity routine is called, which visits
all marked points which can be reached from the start via a connected path. The
marks are erased by this routine as it goes, and statistics are kept on the region
thus generated, such as the sums of the x and y coordinates of the points, and the
sum of the squares of the x and y coordinates (used to compute the centerand the
eccentricity). A tree node is then made up for the region, and the scan for marked
points continues. A special mark is left in the scratch array for each region. When
this mark is encountered during the scan at the next level, it is looked up on an
association list. This establishes the link between a region and the regions which
are a subset of it at the previous level - i.e. between a node and its sub-nodes."
"The contiguity scan is the most complex program. It works by leaving
directional pointers in the scratch array. These are three-bit codes denoting one of
the eight possible neighboring points. The contiguity scan is always started at a
point which is on the bottom edge of the region. It traces along this edge to the
right by moving from one marked point to the next, but always keeping an un-marked
point to the right side. As it goes, it erases the marks, so that for a region with
smooth boundaries, it will follow a spiral path to the center, "eating up" the marks
as it goes, like a lathe with the tool continually advancing into the work."
"As the contiguity routine scans, it lays down back pointers in the scratch
array which enable it to retrace its path back to the start. If a dead end is
reached (no more marked neighbors), it traces back along this path, looking for
marked points to the right. There can be no marked points on the left side while
backtracking, since this was the right side on the way out, and the outgoing scan
stayed as far to the right as possible. If a marked point is found on the backtrace,
it is replaced with a pointer to the adjacent path already traced out, and then a new
path is traced as if this were a new starting point. When the backtrace reaches the
original starting point, the contiguity scan is completed. The effect of this
algorithm is to construct a tree of pointers in the scratch array, with the starting
point at the root. All points which can be reached via a connected path from the
starting point will be a part of this tree."